package nf;

import java.util.*;
import java.math.BigInteger;

import nf.graph.*;

public class GraphGenerator implements Iterable<Graph>
{
	private int nodeCount;
	
	public GraphGenerator(int nodeCount)
	{
		this.nodeCount = nodeCount;
	}
	
	public int getNodeCount()
	{
		return nodeCount;
	}
	
	public Graph generateEmptyGraph()
	{
		return generateEmptyGraph(nodeCount);
	}
	
	public Graph generateLine()
	{
		return generateLine(nodeCount);
	}
	
	public Graph generateCycle()
	{
		return generateCycle(nodeCount);
	}
	
	public Graph generateComplete()
	{
		return generateComplete(nodeCount);
	}
	
	/**
	 * Warning: while the configurations of edges in each graph produced by the
	 * iterator are guaranteed to be distinct, the node and graph objects are
	 * not! Any modifications to groups or to the nodes in the graph should be
	 * made on copied objects.
	 */
	public Iterator<Graph> iterator()
	{
		return new GraphIterator();
	}
	
	public long countPairs()
	{
		long pairs = 0;
		for (int i = 0; i < nodeCount; i++) {
			for (int j = (i + 1); j < nodeCount; j++)
				pairs++;
		}
		return pairs;
	}
	
	private class GraphIterator implements Iterator<Graph>
	{
		private List<Node> nodes;
		private Graph graph;
		private BigInteger stop;
		private BigInteger bits;
		private long pairs;
		private boolean safe;
		
		public GraphIterator()
		{
			pairs = countPairs();
			
			createGraph();
			
			stop = new BigInteger("0");
			bits = new BigInteger("0");
			for (int i = 0; i < pairs; i++) {
				stop = stop.setBit(i);
			}
			
			safe = false;
		}
		
		private void createGraph()
		{
			graph = new UndirectedGraph();
			Group root = new Group();
			graph.setRootGroup(root);
			
			nodes = generateNodes(nodeCount);
			for (Node n : nodes) {
				root.add(n);
			}
		}
	
		public boolean hasNext()
		{
			safe = true;
			return bits.compareTo(stop) <= 0;
		}
		
		public Graph next()
		{
			if (!safe) {
				if (!hasNext()) {
					throw new NoSuchElementException();
				}
			} else {
				safe = false;
			}
			
			int b = 0;
			for (int i = 0; i < nodeCount; i++) {
				for (int j = (i + 1); j < nodeCount; j++) {
					if (bits.testBit(b))
						graph.connect(nodes.get(i), nodes.get(j));
					else
						graph.disconnect(nodes.get(i), nodes.get(j));
					b++;
				}
			}
			bits = bits.add(BigInteger.ONE);
			
			return graph;
		}
		
		public void remove()
		{
			throw new UnsupportedOperationException();
		}
	}
	
	public static Graph generateLine(int nodeCount)
	{
		List<Node> nodes = generateNodes(nodeCount);
		Graph graph = generateEmptyGraph(0);
		Group root = graph.getRootGroup();
		
		Node previousNode = null;
		for (Node node : nodes) {
			root.add(node);
			if (previousNode != null)
				graph.connect(previousNode, node);
			previousNode = node;
		}
		
		return graph;
	}
	
	public static Graph generateCycle(int nodeCount)
	{
		List<Node> nodes = generateNodes(nodeCount);
		Graph graph = generateEmptyGraph(0);
		Group root = graph.getRootGroup();
		
		Node previousNode = null;
		for (Node node : nodes) {
			root.add(node);
			if (previousNode != null)
				graph.connect(previousNode, node);
			previousNode = node;
		}
		if (previousNode != null)
			graph.connect(previousNode, nodes.get(0));
		
		return graph;
	}
	
	public static Graph generateComplete(int nodeCount)
	{
		List<Node> nodes = generateNodes(nodeCount);
		Graph graph = generateEmptyGraph(0);
		Group root = graph.getRootGroup();
		
		for (Node node : nodes) {
			root.add(node);
		}
		
		for (Node head : nodes) {
			for (Node tail : nodes) {
				graph.connect(head, tail);
			}
		}
		
		return graph;
	}

	public static Graph generateRandomGraph(int nodeCount)
	{
		List<Node> nodes = generateNodes(nodeCount);
		Graph graph = generateEmptyGraph(0);
		Group root = graph.getRootGroup();

		for (Node node : nodes) {
			root.add(node);
		}
		
		Random random = new Random();
		
		int numEdges = random.nextInt((nodeCount * (nodeCount - 1)) / 2);
		int edgesAdded = 0;
		while (edgesAdded < numEdges) {
			int a = random.nextInt(nodeCount);
			int b = random.nextInt(nodeCount);
			
			boolean added = graph.connect(nodes.get(a), nodes.get(b));
			if (added)
				edgesAdded++;
		}
		
		return graph;
	}

	public static Graph generateEmptyGraph(int nodeCount)
	{
		Graph graph = new UndirectedGraph();
		Group root = new Group();
		graph.setRootGroup(root);
		
		for (Node node : generateNodes(nodeCount)) {
			root.add(node);
		}
		
		return graph;
	}
	
	public static ArrayList<Node> generateNodes(int howMany)
	{
		return generateNodes(howMany, 1);
	}
	
	public static ArrayList<Node> generateNodes(int howMany, int start)
	{
		ArrayList<Node> nodes = new ArrayList<Node>(howMany);
	
		for (int i = 0; i < howMany; i++) {
			nodes.add(new Node(Integer.toString(start + i)));
		}
		
		return nodes;
	}
	
	public static void main(String... args)
	{
		GraphGenerator gen = new GraphGenerator(Integer.parseInt(args[0]));
		
		for (Graph g : gen) {
			for (Node n : g) {
				System.out.printf("%s:", n.getName());
				for (Node m : n.getNeighbors()) {
					System.out.print(" " + m.getName());
				}
				System.out.println();
			}
			System.out.println("=================");
		}
	}
}
